package com.origin.niuke.dynamic;

/**
 * NC116 把数字翻译成字符串
 * 算法：动态规划
 * 当前字符可以单独翻译, 也可以与前面一个字符一起翻译
 * 单独翻译时, dp[i] = dp[i - 1]; 一起翻译时, dp[i] = dp[i - 1] + dp[i - 2]
 * 特殊：当前字符为 '0' 时, 只能与前面一个字符一起翻译, 当前一个字符不为 '1' 或 '2' 时, 这个字符串无法翻译
 *
 * @author yezh
 * @version 1.0
 * @date 2022/10/29 22:19
 */
public class NC116 {

    public int solve(String nums) {
        if (nums == null || nums.isEmpty()) return 0;
        int n = nums.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            dp[i] = nums.charAt(i - 1) == '0' ? 0 : dp[i - 1];
            if (i > 1 && ((nums.charAt(i - 2) == '1') || (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) <= '6')))
                dp[i] += dp[i - 2];
            if (dp[i] == 0) return 0;
        }
        return dp[n];
    }
}
